Michaël Périn – Exercice sur la minimisation : cas pièges

• initial partition = { {1,2,3} }
• no more splitting:
  • 3 -c-> {1} <-c- 2
  • 3-b->1 ~ 2-b->2 since 1 , 2 in {1,2,3}
  • 3-a->1 ~ 2-a->3 since 1 , 3 in {1,2,3}
  • 3 -c-> {1} <-c- 1
  • 3 -b-> {1} <-b- 1
  • 3-a->1 ~ 1-a->2 since 1 , 2 in {1,2,3}
  • 2 -c-> {1} <-c- 3
  • 2-b->2 ~ 3-b->1 since 2 , 1 in {1,2,3}
  • 2-a->3 ~ 3-a->1 since 3 , 1 in {1,2,3}
  • 2 -c-> {1} <-c- 1
  • 2-b->2 ~ 1-b->1 since 2 , 1 in {1,2,3}
  • 2-a->3 ~ 1-a->2 since 3 , 2 in {1,2,3}
  • 1 -c-> {1} <-c- 3
  • 1 -b-> {1} <-b- 3
  • 1-a->2 ~ 3-a->1 since 2 , 1 in {1,2,3}
  • 1 -c-> {1} <-c- 2
  • 1-b->1 ~ 2-b->2 since 1 , 2 in {1,2,3}
  • 1-a->2 ~ 2-a->3 since 2 , 3 in {1,2,3}
• final partition = { {1,2,3} }
• A1m .pdf, .html

• initial partition = { {0,1,2,3} }

  states 0 / 1 : NOT same accepting status So, {0,1,2,3} is splitted into {0} |_| {1,2,3}

  states 1 / 3 : NOT same behavior on symbol 'a' So, {1,2,3} is splitted into {1,2} |_| {3}

  states 1 / 2 : NOT same behavior on symbol 'a' So, {1,2} is splitted into {1} |_| {2}

• final partition = { {0} , {1} , {2} , {3} }
• A2m .pdf, .html

Il faut

1. complétez l'automate
2. déterminisez l'automate (ce qui fait au passage la complétion)

On peut minimiser un automate non déterministe mais l'algorithme de raffinement des classes d'équivalences est plus subtil (voir minimisation d'automate non déterministe).